package leetcode.method.dynamic_programming;

/**
 * 乘法太多浪费计算时间
 */
public class Program64MinPathSum {

    public Program64MinPathSum() {
    }

    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] sum = new int[row * col];
        sum[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            sum[i] = grid[0][i] + sum[i - 1];
        }
        for (int i = 1; i < row; i++) {
            sum[i * col] = grid[i][0] + sum[(i - 1) * col];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                sum[i * col + j] = Math.min(sum[i * col + j - 1], sum[(i - 1) * col + j]) + grid[i][j];
            }
        }
        return sum[row * col - 1];
    }

    public static void main(String[] args) {
        Program64MinPathSum myStack = new Program64MinPathSum();
        int[][] grid = {
                {1,3,1}
                ,{1,5,1}
                ,{4,2,1}
        };
        System.out.println(myStack.minPathSum(grid));
        int[][] grid1 = {
                {1,2,3}
                ,{4,5,6}
        };
        System.out.println(myStack.minPathSum(grid1));
    }
}
